import java.util.*;

public class Solution5 {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] dp = new boolean[num.length];
        dfs(res,list,dp,num);
        return res;
    }
    private void dfs(ArrayList<ArrayList<Integer>> res,ArrayList<Integer> list,boolean[] dp,int[] num) {
        if(list.size() == num.length) {
            res.add(new ArrayList(list));
            return;
        } 
        for(int i = 0;i<num.length;i++) {
            if(dp[i]) {
                continue;
            } else {
                dp[i] = true;
                list.add(num[i]);
                dfs(res,list,dp,num);
                dp[i] = false;
                list.remove(list.size() - 1);
            }
        }

    }
}